﻿//#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>

#include "common.h"

// 递归函数正常执行的条件：
// 1. 递归函数必须有结束条件，否则会无限递归下去
// 2. 递归函数必须要有向结束条件逼近的逻辑，否则会陷入死递归
// 3. 递归函数必须要递归调用自己

// %d 是打印有符号整数的格式（会有正负数），%u 是打印无符号整数的格式

// 递归函数：输入一个数，将其每一位数字依次输出
void reverse1(unsigned int num)
{
    if (num <= 0) // 递归出口（递归结束条件）
        return;
    reverse1(num / 10); // 递归调用（向结束条件逼近的逻辑，以及参数）
    printf("%d\t", num % 10); // 打印输出最后一位数字

    // 或者可以用以下方式实现
    /* if (num > 9)
           reverse1(num / 10);
       printf("%d\t", num % 10); */
       //所以根据结束条件的不同，递归函数也可以不用返回值
}

// 以上函数（reverse1）使用循环也可以正序打印
void reverse2(unsigned int num)
{
    int temp = 0;
    while (num != 0)  // 可直接写为 while (num)
    {
        temp = num % 10;
        num /= 10;
        printf("%d\t", temp);
    }
}

// 内存分为堆区、栈区和静态区
/* 栈区：存放函数的参数、返回值（也可能放寄存器，取决于语法和编译器）、
      保存上下文信息、局部变量、返回地址等，
      注意函数的每一次调用都会在栈区申请一块空间 */
      // 堆区：存放动态分配的内存，程序运行时动态申请和释放
      // 静态区：存放程序中定义的全局变量、静态变量等，程序运行前就已经分配好内存

      // 写一个函数，求字符串长度（非递归实现）
int str_len1(char* str)
{
    int start = 0; // 局部变量，保存字符串的起始位置
    while (str[start] != '\0')
        ++start;
    /* 可写为 while (*str != '\0')
             {
                 ++str;
                 ++start;
             } */
    return start;
}

// 写一个递归函数，求字符串长度（递归实现，不能创建临时变量）
int str_len2(const char* str) // const修饰str，表示str是只读的
{
    if (str[0] == '\0') // 递归出口（递归结束条件）
        return 0;
    else
        return 1 + str_len2(str + 1);
    // 递归调用（向结束条件逼近的逻辑）不能写为 ++str，会导致指针地址变化
}

// 写一个递归函数，求字符串长度（递归实现，可以创建临时变量）
int str_len3(char* str)
{
    if (str[0] == '\0') // 递归出口（递归结束条件）
        return 0;
    else
        return 1 + str_len3(str + 1);
    // 递归调用（向结束条件逼近的逻辑）可以写为 ++str，不会导致指针地址变化
}

// 写一个函数，求 n 以下的数的阶乘（非递归实现，打印即可）以及对应的阶乘加和
int* factorial1(int n)
{
    int values_and_sum[2] = { 0, 0 };
    int values = 1;
    int i = 1;
    for (i = 1; i <= n; ++i)
    {
        values *= i;
        values_and_sum[0] = values;
        values_and_sum[1] += values;
        printf("%d! = %d\tsum = %d\n", i, values, values_and_sum[1]);
    }
    return values_and_sum; // 返回值是一个数组，存放阶乘和阶乘加和
}

// 写一个递归函数，求 n 以下的数的阶乘（递归实现）
int factorial2(int n)
{
    if (n <= 1) // 递归出口（递归结束条件）
        return 1;
    else
    {
        //printf("%d! = %d\n", n, n * factorial2(n - 1));
        return n * factorial2(n - 1); // 递归调用（向结束条件逼近的逻辑）
    }
}

// 写一个函数，打印斐波那契数列前 n 个数（非递归实现）
int fibonacci1(int n)
{
    int value = 0;
    if (n <= 2)
    {
        value = 1;
        if (n == 1)
            printf("1");
        else
            printf("1 1");
    }
    else
    {
        int prev_prev = 1;
        int prev = 1;
        printf("%d %d ", prev_prev, prev); // 打印数列前 2 个数
        int i = 3;
        while (i <= n)
        {
            value = prev_prev + prev; // 当前数为前两个数之和
            prev_prev = prev; // 当前的上一个数为下次循环的 prev_prev
            prev = value; // 当前数为下次循环的 prev
            printf("%d ", value); // 打印当前数
            ++i;
        }
        // 可以写为 -- 的形式，不用创建局部变量 i
        /* for (n; n > 2; --n)
           {
               value = prev_prev + prev; // 当前数为前两个数之和
               prev_prev = prev; // 当前的上一个数为下次循环的 prev_prev
               prev = value; // 当前数为下次循环的 prev
               printf("%d ", value); // 打印当前数
           } */
    }
    printf("\n");
    return value;
    // 这里的时间复杂度为 O(n)，所以效率很高
}

// 写一个递归函数，求斐波那契数列第 n 个数（递归实现）
int fibonacci2(int n)
{
    if (n <= 2)
        return 1;
    else
        return fibonacci2(n - 1) + fibonacci2(n - 2);
    // 递归调用，这里的时间复杂度为 O(2^n)，效率很低，很可能会导致栈溢出
}

/*总结：不同的场景选择不同的实现方式，要根据具体情况选择最优的实现方式
    即迭代和递归的效率、空间复杂度、适用场景、可读性、易维护性等*/

    // 函数指针有待学习


    // 待学习：
    // 1. 汉罗塔问题
    // 2. 矩阵乘法
    // 3. 快速排序
    // 4. 二分查找
    // 5. 回溯法
